package com.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 47. 全排列 II
 * 搜索回溯
 *
 * @author fy
 * @date 2022/4/27 20:59
 */
public class Solution47 {

    private List<List<Integer>> res;
    private int n;
    // 使用isUsed记录数据是否已经被使用, 加快速度
    private boolean[] isUsed;

    public List<List<Integer>> permuteUnique(int[] nums) {
        res = new ArrayList<>();
        n = nums.length;
        isUsed = new boolean[n];
        // 需要先对数组排序, 让相同的元素在一起
        Arrays.sort(nums);
        dfs(nums, new ArrayList<>());
        return res;
    }

    private void dfs(int[] nums, List<Integer> preList) {
        if (preList.size() == n) {
            res.add(new ArrayList<>(preList));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (!isUsed[i]) {
                // 如果前一次遍历的元素与当前元素一样, 那么跳过当前这次遍历
                if (i > 0 && nums[i - 1] == nums[i] && !isUsed[i - 1]) {
                    continue;
                }
                preList.add(num);
                isUsed[i] = true;
                dfs(nums, preList);
                isUsed[i] = false;
                // 这里如果传的int类型, 用的是index下标
                preList.remove(preList.size() - 1);
            }
        }
    }

}
